<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Exercises
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora019.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora021.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Exercises</H2><A NAME="toc28"></A>
<H3> Merging two lists</H3><OL type=1>
<LI>
 Write a function <TT><A id="a100__1_APPEND/PFcor.ml.tex" href="javascript: void showMessage('1_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 1,APPEND/PFcor.ml.tex,merge1 -->merge_i</SPAN></A></TT>  
which takes as input two integer lists sorted in increasing order and
returns a new sorted list containing the elements of the first two.
<!-- POPUP DEFINITION -->
<layer id="l__1_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","1_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>merge_i<CODE> </CODE>l1<CODE> </CODE>l2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE><TT>(</TT>l1<CODE>,</CODE>l2<TT>)</TT><CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[],_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>l2<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_,[]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>l1<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>h1::t1<CODE>,</CODE>h2::t2<CODE> </CODE>-&gt;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>h1<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE>h2<CODE> </CODE><B>then</B><CODE> </CODE>h1::<TT>(</TT>merge_i<CODE> </CODE>t1<CODE> </CODE>l2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>h2::<TT>(</TT>merge_i<CODE> </CODE>l1<CODE> </CODE>t2<TT>)</TT>;;<BR><CODE>val merge_i : 'a list -&gt; 'a list -&gt; 'a list = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("1_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a general function <TT><A id="a101__2_APPEND/PFcor.ml.tex" href="javascript: void showMessage('2_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 2,APPEND/PFcor.ml.tex,merge2 -->merge</SPAN></A></TT>  
which takes as argument a comparison function and two lists sorted
in this order and returns the list merged in the same
order. The comparison function will be of type
<I>'a </I><I>-&gt;</I><I> 'a </I><I>-&gt;</I><I> bool</I>. 
<!-- POPUP DEFINITION -->
<layer id="l__2_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","2_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>merge<CODE> </CODE>ord_fn<CODE> </CODE>l1<CODE> </CODE>l2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE><TT>(</TT>l1<CODE>,</CODE>l2<TT>)</TT><CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[],_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>l2<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_,[]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>l1<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>h1::t1<CODE>,</CODE>h2::t2<CODE> </CODE>-&gt;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>ord_fn<CODE> </CODE>h1<CODE> </CODE>h2<CODE> </CODE><B>then</B><CODE> </CODE>h1::<TT>(</TT>merge<CODE> </CODE>ord_fn<CODE> </CODE>t1<CODE> </CODE>l2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>h2::<TT>(</TT>merge<CODE> </CODE>ord_fn<CODE> </CODE>l1<CODE> </CODE>t2<TT>)</TT>;;<BR><CODE>val merge : ('a -&gt; 'a -&gt; bool) -&gt; 'a list -&gt; 'a list -&gt; 'a list = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("2_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> <A id="a102__3_APPEND/PFcor.ml.tex" href="javascript: void showMessage('3_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 3,APPEND/PFcor.ml.tex,applymerge -->Apply</SPAN></A>  
this function to two integer lists sorted in decreasing order, then to two
string lists sorted in decreasing order.
<!-- POPUP DEFINITION -->
<layer id="l__3_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","3_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># merge<CODE> </CODE><TT>(</TT><CODE>&gt;</CODE><TT>)</TT><CODE> </CODE><CODE>[</CODE><CODE>4</CODE><CODE>4</CODE>;<CODE>3</CODE><CODE>3</CODE>;<CODE>2</CODE><CODE>2</CODE>;<CODE>1</CODE><CODE>1</CODE><CODE>]</CODE><CODE> </CODE><CODE>[</CODE><CODE>5</CODE><CODE>5</CODE>;<CODE>3</CODE><CODE>0</CODE>;<CODE>1</CODE><CODE>0</CODE><CODE>]</CODE>;;<BR><CODE>- : int list = [55; 44; 33; 30; 22; 11; 10]</CODE><BR># merge<CODE> </CODE><TT>(</TT><CODE>&gt;</CODE><TT>)</TT><CODE> </CODE><CODE>[</CODE><CODE>"my"</CODE>;<CODE> </CODE><CODE>"first"</CODE>;<CODE> </CODE><CODE>"effort"</CODE><CODE>]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE>"wonderful"</CODE>;<CODE>"try"</CODE>;<CODE>"number"</CODE>;<CODE>"1"</CODE><CODE>]</CODE>;;<BR><CODE>- : string list =</CODE><BR><CODE>["wonderful"; "try"; "number"; "my"; "first"; "effort"; "1"]</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("3_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> What <A id="a103__4_APPEND/PFcor.ml.tex" href="javascript: void showMessage('4_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 4,APPEND/PFcor.ml.tex,mergeq1 -->happens</SPAN></A>  
if one of the lists is not in the required decreasing order?
<!-- POPUP DEFINITION -->
<layer id="l__4_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","4_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 If at least one of the lists is not in the given order, then the result
probably won't be.
</span><script language="JavaScript"><!--
  closePopUp("4_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a new <I><A id="a104__5_APPEND/PFcor.ml.tex" href="javascript: void showMessage('5_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 5,APPEND/PFcor.ml.tex,list -->list</SPAN></A></I>  
type in the form of a record containing three fields: the conventional
list, an order function and a boolean indicating whether the list is in
that order.
<!-- POPUP DEFINITION -->
<layer id="l__5_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","5_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>slist<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{l<CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>list;<CODE> </CODE>ord_fn<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE>bool;<CODE> </CODE>is_in_order<CODE> </CODE><CODE>:</CODE><CODE> </CODE>bool};;<BR><CODE>type 'a slist = { l: 'a list; ord_fn: 'a -&gt; 'a -&gt; bool; is_in_order: bool }</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("5_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write the function <TT><A id="a105__6_APPEND/PFcor.ml.tex" href="javascript: void showMessage('6_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 6,APPEND/PFcor.ml.tex,insert -->insert</SPAN></A></TT>  
which adds an element to a list of this type.<BR>
<BR>

<LI> Write a function
<TT><A id="a106__7_APPEND/PFcor.ml.tex" href="javascript: void showMessage('7_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 7,APPEND/PFcor.ml.tex,sort -->sort</SPAN></A></TT> which insertion sorts the elements of a list. 
<!-- POPUP DEFINITION -->
<layer id="l__6_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","6_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE>insert<CODE> </CODE>e<CODE> </CODE>ls<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>insert_rec<CODE> </CODE>e<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>l<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><CODE>[</CODE>e<CODE>]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>h::t<CODE> </CODE>-&gt;<CODE> </CODE><B>if</B><CODE> </CODE>ls<CODE>.</CODE>ord_fn<CODE> </CODE>e<CODE> </CODE>h<CODE> </CODE><B>then</B><CODE> </CODE>e::l<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>h::<TT>(</TT>insert_rec<CODE> </CODE>e<CODE> </CODE>t<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>ls<CODE>.</CODE>is_in_order<CODE> </CODE><B>then</B><CODE> </CODE>{ls<CODE> </CODE><B>with</B><CODE> </CODE>l<CODE>=</CODE>insert_rec<CODE> </CODE>e<CODE> </CODE>ls<CODE>.</CODE>l}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>{ls<CODE> </CODE><B>with</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>e::ls<CODE>.</CODE>l};;<BR><CODE>val insert : 'a -&gt; 'a slist -&gt; 'a slist = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("6_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<!-- POPUP DEFINITION -->
<layer id="l__7_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","7_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE>sort<CODE> </CODE>ls<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>ls<CODE>.</CODE>is_in_order<CODE> </CODE><B>then</B><CODE> </CODE>ls<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><CODE> </CODE>List.fold_right<CODE> </CODE>insert<CODE> </CODE>ls<CODE>.</CODE>l<CODE> </CODE>{l<CODE>=[]</CODE>;<CODE> </CODE>ord_fn<CODE>=</CODE>ls<CODE>.</CODE>ord_fn;<CODE> </CODE>is_in_order<CODE>=</CODE><B>true</B>};;<BR><CODE>val sort : 'a slist -&gt; 'a slist = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("7_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a new function <TT><A id="a107__8_APPEND/PFcor.ml.tex" href="javascript: void showMessage('8_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 8,APPEND/PFcor.ml.tex,merge3 -->merge</SPAN></A></TT>  
for these lists.
<!-- POPUP DEFINITION -->
<layer id="l__8_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","8_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>merge_ls<CODE> </CODE>l1<CODE> </CODE>l2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>l1<CODE>.</CODE>is_in_order<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>l2<CODE>.</CODE>is_in_order<CODE> </CODE><B>then</B><CODE> </CODE>{l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>merge<CODE> </CODE>l1<CODE>.</CODE>ord_fn<CODE> </CODE>l1<CODE>.</CODE>l<CODE> </CODE>l2<CODE>.</CODE>l;<CODE> </CODE>ord_fn<CODE> </CODE><CODE>=</CODE><CODE> </CODE>l1<CODE>.</CODE>ord_fn;<CODE> </CODE>is_in_order<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>true</B>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>List.fold_right<CODE> </CODE>insert<CODE> </CODE>l2<CODE>.</CODE>l<CODE> </CODE>l1<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>l2<CODE>.</CODE>is_in_order<CODE> </CODE><B>then</B><CODE> </CODE><CODE> </CODE>merge_ls<CODE> </CODE>l2<CODE> </CODE>l1<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><CODE> </CODE>merge_ls<CODE> </CODE><TT>(</TT>sort<CODE> </CODE>l1<TT>)</TT><CODE> </CODE>l2;;<BR><CODE>val merge_ls : 'a slist -&gt; 'a slist -&gt; 'a slist = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("8_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script></OL><A NAME="toc29"></A>
<H3> Lexical trees</H3><A NAME="exo-arbrlex"></A>Lexical trees (or <EM>tries</EM>) are used for the representation of
dictionaries. 


<PRE><BR># <B>type</B><CODE> </CODE>lex_node<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Letter<CODE> </CODE><B>of</B><CODE> </CODE>char<CODE> </CODE><CODE>*</CODE><CODE> </CODE>bool<CODE> </CODE><CODE>*</CODE><CODE> </CODE>lex_tree<CODE> </CODE><BR><CODE> </CODE><B>and</B><CODE> </CODE><CODE> </CODE>lex_tree<CODE> </CODE><CODE>=</CODE><CODE> </CODE>lex_node<CODE> </CODE><CODE> </CODE>list;;<BR># <B>type</B><CODE> </CODE>word<CODE> </CODE><CODE>=</CODE><CODE> </CODE>string;;<BR>

</PRE>

The boolean value in <I>lex_node</I> marks the end of a word when it
equals <B>true</B>.
In such a structure, the sequence of words ``fa, false, far, fare, fried,
frieze'' is stored in the following way:
<DIV ALIGN=center>
<IMG SRC="book-ora003.gif">
</DIV>
An asterisk (*) marks the end of a word.
<OL type=1>
<LI>
 Write the function <TT><A id="a108__9_APPEND/PFcor.ml.tex" href="javascript: void showMessage('9_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 9,APPEND/PFcor.ml.tex,exists -->exists</SPAN></A></TT>  
which tests whether a word belongs to a dictionary of type
<I>lex_tree</I>. 
<!-- POPUP DEFINITION -->
<layer id="l__9_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","9_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>exists<CODE> </CODE>w<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>aux<CODE> </CODE>sw<CODE> </CODE>i<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>d<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<CODE> </CODE><TT>(</TT>c<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::t<CODE> </CODE><B>when</B><CODE> </CODE>c<CODE>=</CODE>sw<CODE>.[</CODE>i<CODE>]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><B>then</B><CODE> </CODE>b<CODE> </CODE><B>else</B><CODE> </CODE>exists<CODE> </CODE><TT>(</TT>String.sub<CODE> </CODE>sw<CODE> </CODE><TT>(</TT>i<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>l<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<CODE> </CODE><TT>(</TT>c<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::t<CODE> </CODE>-&gt;<CODE> </CODE>exists<CODE> </CODE>sw<CODE> </CODE>t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>aux<CODE> </CODE>w<CODE> </CODE><CODE>0</CODE><CODE> </CODE><TT>(</TT>String.length<CODE> </CODE>w<TT>)</TT><CODE> </CODE>;;<BR><CODE>val exists : string -&gt; lex_tree -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("9_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a function <TT><A id="a109__10_APPEND/PFcor.ml.tex" href="javascript: void showMessage('10_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 10,APPEND/PFcor.ml.tex,insertd -->insert</SPAN></A></TT>  
which takes a word and a dictionary and returns a new dictionary which
additionally contains this word. If the word is already in the dictionary,
it is not necessary to insert it.
<!-- POPUP DEFINITION -->
<layer id="l__10_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","10_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>insert<CODE> </CODE>w<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>aux<CODE> </CODE>sw<CODE> </CODE>i<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>then</B><CODE> </CODE>d<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>match</B><CODE> </CODE>d<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><CODE>[</CODE>Letter<CODE> </CODE><TT>(</TT>sw<CODE>.[</CODE>i<CODE>],</CODE><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE>,</CODE><CODE> </CODE>insert<CODE> </CODE><TT>(</TT>String.sub<CODE> </CODE>sw<CODE> </CODE><TT>(</TT>i<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>[]<TT>)</TT><CODE>]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>c<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::t<CODE> </CODE><B>when</B><CODE> </CODE>c<CODE>=</CODE>sw<CODE>.[</CODE>i<CODE>]-&gt;</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><B>then</B><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>c<CODE>,</CODE><B>true</B><CODE>,</CODE>l<TT>)</TT><TT>)</TT>::t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>Letter<TT>(</TT>c<CODE>,</CODE>b<CODE>,</CODE>insert<CODE> </CODE><TT>(</TT>String.sub<CODE> </CODE>sw<CODE> </CODE><TT>(</TT>i<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>l<TT>)</TT>::t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>c<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::t<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>Letter<TT>(</TT>c<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::<TT>(</TT>insert<CODE> </CODE>sw<CODE> </CODE>t<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>aux<CODE> </CODE>w<CODE> </CODE><CODE>0</CODE><CODE> </CODE><TT>(</TT>String.length<CODE> </CODE>w<TT>)</TT><CODE> </CODE>;;<BR><CODE>val insert : string -&gt; lex_tree -&gt; lex_tree = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("10_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a function <TT><A id="a110__11_APPEND/PFcor.ml.tex" href="javascript: void showMessage('11_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 11,APPEND/PFcor.ml.tex,construct -->construct</SPAN></A></TT>  
which takes a list of words and constructs the corresponding dictionary.
<!-- POPUP DEFINITION -->
<layer id="l__11_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","11_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE>construct<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>aux<CODE> </CODE>l<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>l<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>d<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>h::t<CODE> </CODE>-&gt;<CODE> </CODE>aux<CODE> </CODE>t<CODE> </CODE><TT>(</TT>insert<CODE> </CODE>h<CODE> </CODE>d<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>aux<CODE> </CODE>l<CODE> </CODE>[]<CODE> </CODE>;;<BR><CODE>val construct : string list -&gt; lex_tree = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("11_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a function <TT><A id="a111__12_APPEND/PFcor.ml.tex" href="javascript: void showMessage('12_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 12,APPEND/PFcor.ml.tex,filter -->verify</SPAN></A></TT>  
which takes a list of words and a dictionary and returns the list of words
not belonging to this dictionary.
<!-- POPUP DEFINITION -->
<layer id="l__12_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","12_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>filter<CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>h::t<CODE> </CODE>-&gt;<CODE> </CODE><B>if</B><CODE> </CODE>p<CODE> </CODE>h<CODE> </CODE><B>then</B><CODE> </CODE>h::<TT>(</TT>filter<CODE> </CODE>p<CODE> </CODE>t<TT>)</TT><CODE> </CODE><B>else</B><CODE> </CODE>filter<CODE> </CODE>p<CODE> </CODE>t<CODE> </CODE>;;<BR><CODE>val filter : ('a -&gt; bool) -&gt; 'a list -&gt; 'a list = &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>verify<CODE> </CODE>l<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE>filter<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>not<CODE> </CODE><TT>(</TT>exists<CODE> </CODE>x<CODE> </CODE>d<TT>)</TT><TT>)</TT><CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>val verify : string list -&gt; lex_tree -&gt; string list = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("12_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a function <TT><A id="a112__13_APPEND/PFcor.ml.tex" href="javascript: void showMessage('13_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 13,APPEND/PFcor.ml.tex,select -->select</SPAN></A></TT>  
which takes a dictionary and a length and returns the set of words of this
length.
<!-- POPUP DEFINITION -->
<layer id="l__13_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","13_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE>string_of_char<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>String.make<CODE> </CODE><CODE>1</CODE><CODE> </CODE>c<CODE> </CODE>;;<BR><CODE>val string_of_char : char -&gt; string = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>select<CODE> </CODE>n<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>d<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>c<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::t<CODE> </CODE><B>when</B><CODE> </CODE>n<CODE>=</CODE><CODE>1</CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>f<CODE> </CODE><TT>(</TT>Letter<CODE> </CODE><TT>(</TT>c<CODE>,</CODE>b<CODE>,_</CODE><TT>)</TT><TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>if</B><CODE> </CODE>b<CODE> </CODE><B>then</B><CODE> </CODE>string_of_char<CODE> </CODE>c<CODE> </CODE><B>else</B><CODE> </CODE><CODE>"!"</CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>filter<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x<CODE> </CODE><CODE>&lt;&gt;</CODE><CODE> </CODE><CODE>"!"</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>List.map<CODE> </CODE>f<CODE> </CODE>d<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Letter<TT>(</TT>c<CODE>,</CODE>b<CODE>,</CODE>l<TT>)</TT><TT>)</TT>::t<CODE> </CODE>-&gt;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>r1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>select<CODE> </CODE><TT>(</TT>n<CODE>-</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE>l<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>r2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>select<CODE> </CODE>n<CODE> </CODE>t<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>pr<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.map<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>s<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>string_of_char<CODE> </CODE>c<TT>)</TT><CODE>^</CODE>s<TT>)</TT><CODE> </CODE>r1<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>pr<CODE>@</CODE>r2<CODE> </CODE>;;<BR><CODE>val select : int -&gt; lex_tree -&gt; string list = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("13_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script></OL><A NAME="toc30"></A>
<H3> Graph traversal</H3>We define a type <I>'a graph</I> representing directed graphs by
adjacency lists containing for each vertex the list of its successors:


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>graph<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE> </CODE><I>'a</I><CODE> </CODE><CODE>*</CODE><CODE> </CODE><I>'a</I><CODE> </CODE><CODE> </CODE>list<TT>)</TT><CODE> </CODE>list<CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
<OL type=1>
<LI>
 Write a function <TT><A id="a113__14_APPEND/PFcor.ml.tex" href="javascript: void showMessage('14_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 14,APPEND/PFcor.ml.tex,insertvtx -->insert_vtx</SPAN></A></TT>  
which inserts a vertex into a graph and returns the new graph.
<!-- POPUP DEFINITION -->
<layer id="l__14_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","14_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>insert_vtx<CODE> </CODE>v<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>g<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><CODE>[</CODE><TT>(</TT>v<CODE>,[]</CODE><TT>)</TT><CODE>]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>h<CODE>,_</CODE><TT>)</TT><CODE>::_</CODE><CODE> </CODE><B>when</B><CODE> </CODE>h<CODE>=</CODE>v<CODE> </CODE>-&gt;<CODE> </CODE>failwith<CODE> </CODE><CODE>"existing vertex"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>vl::t<CODE> </CODE>-&gt;<CODE> </CODE>vl::<TT>(</TT>insert_vtx<CODE> </CODE>v<CODE> </CODE>t<TT>)</TT><CODE> </CODE>;;<BR><CODE>val insert_vtx : 'a -&gt; ('a * 'b list) list -&gt; ('a * 'b list) list = &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>insert_vtx<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>insert_vtx<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>graph<CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>graph<TT>)</TT><CODE> </CODE>;;<BR><CODE>val insert_vtx : 'a -&gt; 'a graph -&gt; 'a graph = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("14_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a function <TT><A id="a114__15_APPEND/PFcor.ml.tex" href="javascript: void showMessage('15_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 15,APPEND/PFcor.ml.tex,insertedge -->insert_edge</SPAN></A></TT>  
which adds an edge to a graph already possessing these two vertices.
<!-- POPUP DEFINITION -->
<layer id="l__15_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","15_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>insert_edge<CODE> </CODE>v1<CODE> </CODE>v2<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>g<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>failwith<CODE> </CODE><CODE>"unknown vertex"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>h<CODE>,</CODE>el<TT>)</TT>::t<CODE> </CODE><B>when</B><CODE> </CODE>h<CODE>=</CODE>v1<CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>List.mem<CODE> </CODE>v2<CODE> </CODE>el<CODE> </CODE><B>then</B><CODE> </CODE>failwith<CODE> </CODE><CODE>"existing edge"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT>v1<CODE>,</CODE>v2::el<TT>)</TT>::t<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>vl::t<CODE> </CODE>-&gt;<CODE> </CODE>vl::<TT>(</TT>insert_edge<CODE> </CODE>v1<CODE> </CODE>v2<CODE> </CODE>t<TT>)</TT><CODE> </CODE>;;<CODE> </CODE><BR><CODE>val insert_edge : 'a -&gt; 'b -&gt; ('a * 'b list) list -&gt; ('a * 'b list) list =</CODE><BR><CODE>  &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>insert_edge<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>insert_edge<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>graph<CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>graph<CODE> </CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val insert_edge : 'a -&gt; 'a -&gt; 'a graph -&gt; 'a graph = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("15_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a function <TT><A id="a115__16_APPEND/PFcor.ml.tex" href="javascript: void showMessage('16_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 16,APPEND/PFcor.ml.tex,hasedgesto -->has_edges_to</SPAN></A></TT>  
which returns all the vertices following directly from a given vertex.
<!-- POPUP DEFINITION -->
<layer id="l__16_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","16_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>has_edges_to<CODE> </CODE>v<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>g<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>v<CODE>'</CODE><CODE>,</CODE>el<TT>)</TT><CODE>::_</CODE><CODE> </CODE><B>when</B><CODE> </CODE>v<CODE>=</CODE>v<CODE>'</CODE><CODE> </CODE>-&gt;<CODE> </CODE>el<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_::</CODE>t<CODE> </CODE>-&gt;<CODE> </CODE>has_edges_to<CODE> </CODE>v<CODE> </CODE>t<CODE> </CODE>;;<CODE> </CODE><BR><CODE>val has_edges_to : 'a -&gt; ('a * 'b list) list -&gt; 'b list = &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>has_edges_to<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>has_edges_to<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>graph<CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>list<TT>)</TT><CODE> </CODE>;;<BR><CODE>val has_edges_to : 'a -&gt; 'a graph -&gt; 'a list = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("16_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>

<LI> Write a function <TT><A id="a116__17_APPEND/PFcor.ml.tex" href="javascript: void showMessage('17_APPEND/PFcor.ml.tex')" class="mousable"><SPAN style=""><!-- 17,APPEND/PFcor.ml.tex,hasedgesfrom -->has_edges_from</SPAN></A></TT>  
which returns the list of all the vertices leading directly to a given
vertex.
<!-- POPUP DEFINITION -->
<layer id="l__17_APPEND/PFcor.ml.tex" class="hint" style="visibility:hidden; position:absolute" visibility="hide"  width="50%">
<script language="JavaScript"><!--
  openPopUp("50%","17_APPEND/PFcor.ml.tex","");
// --></script><span style="">
 

<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>has_edges_from<CODE> </CODE>v<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>g<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>[]<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>h<CODE>,</CODE>el<TT>)</TT>::t<CODE> </CODE>-&gt;<CODE> </CODE><B>if</B><CODE> </CODE>List.mem<CODE> </CODE>v<CODE> </CODE>el<CODE> </CODE><B>then</B><CODE> </CODE>h::<TT>(</TT>has_edges_to<CODE> </CODE>v<CODE> </CODE>t<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT>has_edges_to<CODE> </CODE>v<CODE> </CODE>t<TT>)</TT><CODE> </CODE>;;<BR><CODE>val has_edges_from : 'a -&gt; ('a * 'a list) list -&gt; 'a list = &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>has_edges_from<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>has_edges_from<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>graph<CODE> </CODE>-&gt;<CODE> </CODE><I>'a</I><CODE> </CODE>list<TT>)</TT><CODE> </CODE>;;<BR><CODE>val has_edges_from : 'a -&gt; 'a graph -&gt; 'a list = &lt;fun&gt;</CODE><BR>

</PRE>

</span><script language="JavaScript"><!--
  closePopUp("17_APPEND/PFcor.ml.tex");
// --></script></layer><!-- END OF POPUP -->
<script language="JavaScript"><!--
  initializePreviousHints();
// --></script><BR>
<BR>
 </OL><HR>
<A HREF="book-ora019.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora021.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
